package club.vann.nowcoder;

import club.vann.nowcoder.common.ListNode;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * <p>难度：Hard</p>
 * <p>题目：合并K个已排序的链表</p>
 * <p>描述：合并\ k k 个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。
 * 示例1
 * 输入
 * 复制
 * [{1,2,3},{4,5,6,7}]
 * 返回值
 * 复制
 * {1,2,3,4,5,6,7}</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-10:15:51:32
 */
public class NC51 {
    public static void main(String[] args) {
        NC51 nc51 = new NC51();

        System.out.println("Result[");
    }

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.size() == 0) {
            return null;
        }
        int len = lists.size();
        if(len == 1) {
            return lists.get(0);
        }
        ListNode base = lists.get(0);
        for(int i = 1; i < len; i ++) {
            base = mergeList(base, lists.get(i));
        }
        return base;
    }

    private ListNode mergeList(ListNode base, ListNode node) {
        ListNode head = new ListNode(Integer.MIN_VALUE);
        ListNode pre = head;
        while(base != null || node != null) {
            if(base != null && node != null) {
                if(base.val <= node.val) {
                    pre.next = base;
                    base = base.next;
                } else {
                    pre.next = node;
                    node = node.next;
                }
                pre = pre.next;
            } else if(base != null) {
                pre.next = base;
            } else {
                pre.next = node;
            }
            pre = pre.next;

        }

        return head.next;
    }

    static class TestCase {
        public static ListNode ANS = ListNode.deserialize("[]");
        public static ArrayList<ListNode> funt() {
            ArrayList<ListNode> ans = new ArrayList<>();
            ans.add(ListNode.deserialize("[1,2,3]"));
            ans.add(ListNode.deserialize("[4,5,6,7]"));
            return ans;
        }
    }
}
